from random import randint
import random

random.seed(112)
test_list = [randint(1, 100) for i in range(10)]
print(test_list)


def partition(nums, left, right):
    """
    先取一个参考数，这里使用第一个数，也可以随机取，或取中点，
    从数组最右边的数和参考数进行比较，如比参考数大，right标减少，一直到比参考数小为止
    重数组最左边的数和参考数进行比较，如比参考数小，left标增加，一直到比查考数大为止
    交换right,和right标对应的数，并对right和right分别进行减少和增加
    """
    midVal = nums[left]
    while left < right:
        while left < right and nums[right] >= midVal:
            right -= 1
        else:
            nums[left] = nums[right]

        while left < right and nums[left] <= midVal:
            left += 1
        else:
            nums[right] = nums[left]
    nums[left] = midVal
    return left


def sort(arr, left, right):
    print(left, right)
    if left >= right:
        return
    partitionNum = partition(arr, left, right)
    print(partitionNum)
    print(arr)
    sort(arr, left, partitionNum - 1)
    sort(arr, partitionNum + 1, right)


def quick_sort(test):
    """
    快速排序：在数组任选一个数字，比该数字小的分为左子组，比该数字小的分为右子组，然后递归对各子组进行相同操作，递归终止条件为子组无法分。
    :param test:
    :return:
    """
    sort(test, 0, len(test) - 1)

    return test


print(quick_sort(test_list))
